package com.github.yangyishe.p100;

/**
 * 70. 爬楼梯
 * https://leetcode.cn/problems/climbing-stairs/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：2
 * 解释：有两种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶
 * 2. 2 阶
 * 示例 2：
 *
 * 输入：n = 3
 * 输出：3
 * 解释：有三种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶 + 1 阶
 * 2. 1 阶 + 2 阶
 * 3. 2 阶 + 1 阶
 *
 *
 * 提示：
 *
 * 1 <= n <= 45
 */
public class Problem70 {
    public static void main(String[] args) {
        int n=5;

        Problem70 problem70 = new Problem70();
        int stairs = problem70.climbStairs(n);
        System.out.println("stairs = " + stairs);

    }

    /**
     * 思路:
     * 不妨先考虑前面几个阶梯时的可能
     * n=1: 1种. (1+0)
     * n=2: 2种. 2; 1+1. (1+1)
     * n=3: 3种. 2+1; 1+2; 1+1+1. (2+1)
     * n=4: 5种. 2+2; 2+1+1; 1+2+1; 1+1+2; 1+1+1+1. (3+2)
     * n=5: ?种. 2+2+1; ()
     *
     * 楼梯数为n时的方案, 可以拆分为p+q. 其中p表示最后一次走一步的情况, q表示最后一次走2步的情况.
     * 则n+1的方案数量. 最后一次走一步的情况为p+q., 最后一次走2步的情况数为p.
     *
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        //1. 创建一个数字二维数组, 分别表示p和q的数量
        int[][] nums=new int[n][2];
        nums[0][0]=1;
        nums[0][1]=0;

        //2. 遍历推进, 计算p+q
        for(int i=1;i<n;i++){
            nums[i][0]=nums[i-1][0]+nums[i-1][1];
            nums[i][1]=nums[i-1][0];
        }

        //3. 返回p+q
        return nums[n-1][0]+nums[n-1][1];
    }
}
